In a communication system, it is necessary to artificially add redundant codes to the data stream according to certain rules before information is sent so that a receiving terminal can detect and correct error codes. RS error correction code is currently one of the most effective and widely used error control encoding measures. RS codes can be used to correct random errors, and are also suitable for correcting burst errors, and have been widely used in areas such as satellite communications, digital television transmission or the like.
(c, k, 2t) are typically used to represent RS codes; where c is the total length of information data and redundant code, k is the length of the information data, 2t is the length of the redundant code, and t is the maximum number of errors that can be corrected, where c=K+2t.
The number of elements in the Galois field (GF) in the conventional RS error correction algorithm is related to the number of primitive polynomials. For example, if the order of a primitive polynomials is 8, then the number of elements in the GF is 28, i.e., 256, the elements in the GF are used for a lookup table in the RS error correction calculation process, and the number of elements in the lookup table reaches 256; and if the order of a primitive polynomial is 16, then the number of elements in the GF is 216, i.e., 65536, which occupies more memory space, and therefore the speed of data processing is slow and the application thereof is limited. In addition, if the number of actual error code words exceeds the error correction capacity, a situation that more errors occur as the error correction proceeds may arise.
In addition, in conventional RS error correction algorithms, the error codes are not checked after being found and corrected, so the stability and correctness of the system is not high.
Chinese invention patent publication No. CN1303763C discloses a method for reducing the complexity of encoding and decoding RS codes. The invention has the following main features: when encoding at a sending terminal, the code element of the RS code is represented by the power of the primitive field element α, and code words of the RS codes are all in the finite field GF(2m), and all non-zero elements in the finite field GF(2m) are integer powers of the primitive field element α. In coding and decoding, for any two elements X and Y in the finite field GF(2m), multiplication of X and Y equals to addition of the corresponding two exponents, and the addition and subtraction of X and Y are performed using a lookup table. In this way, the coding and decoding method is improved based on existing RS coding and decoding algorithms, the complicated multiplication operation can be avoided and the coding and decoding speed is improved. However, for the finite field GF(2m), three lookup tables have to be established, i and x′ in each group are stored in two long lookup tables, power [ ] and index [ ], and there is a further lookup table f(s), where s is selected from all the integers ranging from 0 to 2m−1, with a total number of 2m. While the calculation speed is fast, the data memory occupied is relatively large, and after the RS error codes are corrected using the redundant codes, no valid data are used for checking, resulting in low security and stability.